#include <cstdlib>
#include <iostream>
#include <vector>
#include <fstream>


void pointrandom(int n, int point[][2]);
void distances(int n, int m, int point[][2], int edge[][3]);
void affichage(int n, int m, int point[][2], int edge[][3]);
void tri(int m, int edge[][3]);
void Kruskal(int n, int edge[][3], int arbre[][2]);
void AffichageGraphique(int n, int point[][2], int arbre[][2]);

using namespace std;

int main()
{
	
  int n;             //Le nombre de points.
cout<<"Entrer le nombre de points: "<<endl;
cin>>n;
  int m=n*(n-1)/2;   // Le nombre de paires de points.
  int point[1000][2];   // Les coordonnees des points dans le plan.
  int edge[10000][3];    // Les paires de points et le carre de leur longueur.
  int arbre[999][2]; // Les aretes de l'arbre de Kruskal.
	pointrandom(n, point);
	distances( n, m, point,edge);
	tri(m, edge);
	Kruskal(n, edge ,arbre);
	AffichageGraphique(n, point, arbre);

  return 0;
}

void pointrandom(int n, int point[][2])
{
	
		srand(time(NULL));

		int i;
		for(i=0;i<n;i++){

			point[i][0]=rand()%612;
			point[i][1]=rand()%792;

		}




}


void distances(int n, int m, int point[][2], int edge[][3])
{

		int k=0;


			for(int i(0); i<n-1; i++){

				for(int  j(i+1); j<n; j++){

					edge[k][0]=i;
					edge[k][1]=j;
					edge[k][2]=((point[i][0]-point[j][0])*(point[i][0]-point[j][0]))+((point[i][1]-point[j][1])*
					(point[i][1]-point[j][1]));
					k++;
				}

			}





}


	void affichage(int n, int m, int point[][2], int edge[][3])
{
    for(int i(0); i < n; i++)
    {
    cout<< "point[" << i << "][0]=" << point[i][0] << " point[" << i << "][1]=" << point[i][1] << endl;
    }
    for(int j(0); j < m; j++)
    {
    cout << "edge[" << j << "][0]=" << edge[j][0] << " edge[" << j << "][1]" << edge[j][1] << " distances " << edge[j][0] << "//" << edge[j][1] << "=" << edge[j][2] << endl;
    }
}






void tri(int m, int edge[][3])
{

	bool ex;
	int temp[1][3];
        do{
		ex=false;
		for(int j(0); j<m-1; j++){

			if(edge[j][2]>edge[j+1][2]){

	
				temp[0][0]=edge[j][0];
		 		temp[0][1]=edge[j][1];
				temp[0][2]=edge[j][2];

				edge[j][0]=edge[j+1][0];
				edge[j][1]=edge[j+1][1];
				edge[j][2]=edge[j+1][2];

				edge[j+1][0]=temp[0][0];
				edge[j+1][1]=temp[0][1];
				edge[j+1][2]=temp[0][2];

				

                 		ex = true;
			}
		}
        }while(ex);
}




void Kruskal(int n, int edge[][3],int arbre[999][2])
{
	int cpt=0;
	int aux;
	int comp[10000];

		for(int i(0); i<n;i++){
		
			comp[i]=i;
			
		}

		for(int j(0); j<n*(n-1)/2; j++)
		{

			if(comp[edge[j][0]]!=comp[edge[j][1]])
			{	
		

				if(comp[edge[j][0]]!=comp[edge[j][1]]) //question 4.2
				{
					aux=comp[edge[j][0]];
					arbre[cpt][0]=edge[j][0];
					arbre[cpt][1]=edge[j][1];
					
					cpt++;
					
		
					for(int k(0); k<n; k++)
					{

						if(comp[k]==aux)
							comp[k]=comp[edge[j][1]];
				
					
					}
				}
			}
		}
}

void AffichageGraphique(int n, int point[][2], int arbre[][2])       // Cree le fichier Exemple.ps qui affiche
                                                                     // les points et l'arbre de Kruskal.
{	ofstream output;                           
	output.open("Exemple.ps",ios::out);
	output << "%!PS-Adobe-3.0" << endl;
	output << "%%BoundingBox: 0 0 612 792" << endl;
	output << endl;  
	for(int i=0;i<n;i++)
	{	output << point[i][0] << " " << point[i][1] << " 3 0 360 arc" <<endl;
		output << "0 setgray" <<endl;
		output << "fill" <<endl;
		output << "stroke"<<endl;
		output << endl;
	}
	output << endl;
	for(int i=0;i<n-1;i++)
	{	output << point[arbre[i][0]][0] << " " << point[arbre[i][0]][1] 
		<< " moveto" << endl;
		output << point[arbre[i][1]][0] << " " << point[arbre[i][1]][1] 
		<< " lineto" << endl;
		output << "stroke" << endl;
		output << endl;
	}
}





